package com.lw.leetcode.arr.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 954. 二倍数对数组
 *
 * @Author liw
 * @Date 2021/6/21 17:12
 * @Version 1.0
 */
public class CanReorderDoubled {

    public static void main(String[] args) {
        CanReorderDoubled test = new CanReorderDoubled();
//        int[] arr = {4,-2,2,-4};
//        int[] arr = {1,2,4,16,8,4};

        // [-1,4,6,8,-4,6,-6,3,-2,3,-3,-8]
        int[] arr = {-1,4,6,8,-4,6,-6,3,-2,3,-3,-8};
        boolean b = test.canReorderDoubled(arr);
        System.out.println(b);
    }

    public boolean canReorderDoubled(int[] arr) {
        Arrays.sort(arr);
        int length = arr.length;
        Map<Long, Integer> map = new HashMap<>(length << 1);
        long key;
        long key2;
        for (int i = 0; i < length; i++) {
            key = arr[i] << 1;
            map.merge(key, 1, (a, b) -> a + b);
        }
        for (int num : arr) {
            key = num;
            Integer value = map.get(key);
            if (value == null || value == 0) {
                continue;
            }

            key2 = num << 1;
            Integer value2 = map.get(key2);
            if (value2 == null || value2 == 0) {
                continue;
            }
            map.put(key, value - 1);
            map.put(key2, value2 - 1);
        }
        for (Map.Entry<Long, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) {
                return false;
            }
        }
        return true;
    }
}
